package com.sheng.leetcode.year2022.swordfingeroffer.day16;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/09/14
 *<p>
 * 剑指 Offer 45. 把数组排成最小的数<p>
 *<p>
 * 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。<p>
 *<p>
 * 示例 1:<p>
 * 输入: [10,2]<p>
 * 输出: "102"<p>
 *<p>
 * 示例2:<p>
 * 输入: [3,30,34,5,9]<p>
 * 输出: "3033459"<p>
 *<p>
 * 提示:<p>
 *<p>
 * 0 < nums.length <= 100<p>
 * 说明:<p>
 *<p>
 * 输出结果可能非常大，所以你需要返回一个字符串而不是整数<p>
 * 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword0045 {

    @Test
    public void test01() {
//        int[] nums = {10,2};
//        int[] nums = {3,30,34,5,9};
//        int[] nums = {824,938,1399,5607,6973,5703,9609,4398,8247};
        int[] nums = {121,12};
        System.out.println(new Solution().minNumber(nums));
    }
}
class Solution {
    public String minNumber(int[] nums) {
        int length = nums.length;
        // 将int数组变为string数组
        String[] strs = new String[length];
        for (int i = 0; i < length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        // 对string数组进行排序
        Arrays.sort(strs, (str1, str2) -> {
            int length1 = str1.length();
            int length2 = str2.length();
            int index1 = 0, index2 = 0;
            // 按照顺序比较字符的大小
            while (index1 <= length1 && index2 <= length2) {
                // str1和str2全部到达边界时，比较最后一个字符是否相等，相等则比较字符串场地
                if (index1 == length1 && index2 == length2) {
                    return str1.charAt(length1 - 1) == str2.charAt(length2 - 1) ? length1 - length2 : str1.charAt(length1 - 1) - str2.charAt(length2 - 1);
                } else if (index1 == length1) {
                    // 如果str1先到达边界，则比较str1的第一个字符和str2后续字符的大小
                    if (str1.charAt(0) == str2.charAt(index2)) {
                        // 相等时，str2往后再移动一位
                        index2++;
                    } else {
                        // 不相等直接输出
                        return str1.charAt(0) - str2.charAt(index2);
                    }
                } else if (index2 == length2) {
                    // 如果str2先到达边界，则比较str2的第一个字符和str1后续字符的大小
                    if (str1.charAt(index1) == str2.charAt(0)) {
                        // 相等时，str1往后再移动一位
                        index1++;
                    } else {
                        // 不相等直接输出
                        return str1.charAt(index1) - str2.charAt(0);
                    }
                } else if (str1.charAt(index1) == str2.charAt(index2)) {
                    // 如果字符相等，同时往后移动一位
                    index1++;
                    index2++;
                } else {
                    // 字符不相等直接输出
                    return str1.charAt(index1) - str2.charAt(index2);
                }
            }
            return 0;
        });
        // 排序后按顺序进行拼接
        StringBuilder str = new StringBuilder();
        for (String s : strs) {
            str.append(s);
        }
        return str.toString();
    }
}

//class Solution {
//    public String minNumber(int[] nums) {
//        String[] strs = new String[nums.length];
//        for(int i = 0; i < nums.length; i++)
//            strs[i] = String.valueOf(nums[i]);
//        quickSort(strs, 0, strs.length - 1);
//        StringBuilder res = new StringBuilder();
//        for(String s : strs)
//            res.append(s);
//        return res.toString();
//    }
//    void quickSort(String[] strs, int l, int r) {
//        if(l >= r) return;
//        int i = l, j = r;
//        String tmp = strs[i];
//        while(i < j) {
//            while((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j) j--;
//            while((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j) i++;
//            tmp = strs[i];
//            strs[i] = strs[j];
//            strs[j] = tmp;
//        }
//        strs[i] = strs[l];
//        strs[l] = tmp;
//        quickSort(strs, l, i - 1);
//        quickSort(strs, i + 1, r);
//    }
//}
//
//作者：jyd
//链接：https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/solution/mian-shi-ti-45-ba-shu-zu-pai-cheng-zui-xiao-de-s-4/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
